#define _CRT_SECURE_NO_WARNINGS 1
class Solution
{
    int n;
    vector<string> ret;
    string path;
    int left = 0, right = 0;
public:
    void dfs()
    {
        if (right == n)
        {
            ret.push_back(path);
            return;
        }
        if (left < n)
        {
            path.push_back('(');
            left++;
            dfs();
            left--;
            path.pop_back();
        }
        if (right < left)
        {
            path.push_back(')');
            right++;
            dfs();
            right--;
            path.pop_back();
        }
    }
    vector<string> generateParenthesis(int _n)
    {
        n = _n;
        dfs();

        return ret;
    }
};
class Solution
{
    int dx[4] = { 1, -1, 0, 0 };
    int dy[4] = { 0, 0, 1, -1 };
    vector<vector<bool>> vis;
    int m, n;
public:
    bool dfs(vector<vector<char>>& board, int a, int b, string& word, int pos)
    {
        if (pos == word.size()) return true;
        for (int i = 0; i < 4; i++)
        {
            int x = a + dx[i];
            int y = b + dy[i];
            if (x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos])
            {
                vis[x][y] = true;
                if (dfs(board, x, y, word, pos + 1)) return true;
                vis[x][y] = false;
            }
        }
        return false;
    }
    bool exist(vector<vector<char>>& board, string word)
    {
        m = board.size(), n = board[0].size();
        vis = vector<vector<bool>>(m, vector<bool>(n));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (board[i][j] == word[0])
                {
                    vis[i][j] = true;
                    if (dfs(board, i, j, word, 1)) return true;
                    vis[i][j] = false;
                }
            }
        }

        return false;
    }
};
class Solution
{
    vector<vector<int>> ret;
    vector<int> path;
    int sum = 0;
    int target;
public:
    void dfs(vector<int>& candidates, int pos)
    {
        if (sum > target) return;
        else if (sum == target)
        {
            ret.push_back(path);
            return;
        }

        for (int i = pos; i < candidates.size(); i++)
        {
            sum += candidates[i];
            path.push_back(candidates[i]);
            dfs(candidates, i);
            sum -= candidates[i];
            path.pop_back();
        }


    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
    {
        target = _target;
        dfs(candidates, 0);
        return ret;
    }
};
class Solution
{
    vector<string> ret;
    string path;
    vector<string> hash = { "", "", "abc", "def","ghi","jkl","mno","pqrs","tuv","wxyz" };
public:
    void dfs(string& digits, int pos)
    {
        if (pos == digits.size())
        {
            ret.push_back(path);
            return;
        }
        for (auto ch : hash[digits[pos] - '0'])
        {
            path.push_back(ch);
            dfs(digits, pos + 1);
            path.pop_back();
        }
    }
    vector<string> letterCombinations(string digits)
    {
        if (digits.size() == 0) return {};
        dfs(digits, 0);
        return ret;
    }
};
class Solution
{
    vector<vector<int>> ret;
    vector<int> path;

public:
    void dfs(vector<int>& nums, int pos)
    {
        ret.push_back(path);
        if (pos == nums.size()) return;
        for (int i = pos; i < nums.size(); i++)
        {
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums)
    {
        dfs(nums, 0);

        return ret;
    }
};
class Solution
{
    vector<int> path;
    vector<vector<int>> ret;
    vector<bool> IsUse;
    int n;
public:
    void dfs(vector<int>& nums)
    {
        if (path.size() == n)
        {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++)
        {
            if (!IsUse[i])
            {
                path.push_back(nums[i]);
                IsUse[i] = true;
                dfs(nums);
                path.pop_back();
                IsUse[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums)
    {
        n = nums.size();
        IsUse = vector<bool>(n);
        dfs(nums);
        return ret;
    }
};
class Trie
{
    struct Node
    {
        Node() {};
        Node(char c) :ch(c)
        {}
        char ch;
        struct Node* child[26] = { nullptr };
        bool isend = false;
    };

    Node* root;
public:
    Trie()
    {
        root = new Node;
    }

    void insert(string word)
    {
        Node* cur = root;
        for (int i = 0; i < word.size(); i++)
        {
            char ch = word[i];

            if (!cur->child[ch - 'a'])
            {
                Node* newnode = new Node(ch);
                cur->child[ch - 'a'] = newnode;
            }
            cur = cur->child[ch - 'a'];

            if (i == word.size() - 1) cur->isend = true;
        }

    }

    bool search(string word)
    {
        Node* cur = root;
        for (int i = 0; i < word.size(); i++)
        {
            char ch = word[i];
            if (cur->child[ch - 'a'])
            {
                cur = cur->child[ch - 'a'];
            }
            else return false;
            if (i == word.size() - 1)
            {
                if (cur->isend == true) return true;
                else return false;
            }
        }
        return false;

    }

    bool startsWith(string prefix)
    {
        Node* cur = root;
        for (int i = 0; i < prefix.size(); i++)
        {
            char ch = prefix[i];
            if (cur->child[ch - 'a'])
            {
                cur = cur->child[ch - 'a'];
            }
            else return false;
        }
        return true;
    }
};


